class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;

        // 假设target存在
        // 若某一次比较，mid为target，则r=true_mid-1，最终l增加=r+1>r且=true_mid
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public int searchInsertRecur(int[] nums, int target) {
        int n = nums.length;
        return binarySearch(nums, 0, n - 1, target);
    }

    private int binarySearch(int[] nums, int left, int right, int target) {
        if (left >= right) {
            if (nums[left] < target) {
                return left + 1;
            } else {
                return left;
            }
        }

        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) {
            return mid;
        }
        if (left < right) {
            if (nums[mid] > target) {
                return binarySearch(nums, left, mid - 1, target);
            } else {
                return binarySearch(nums, mid + 1, right, target);
            }
        }
        return mid;
    }
}